#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=1e5+10,MOD=1e6;
int n,m,s,t,a[MAXN],f[2][MAXN],g[2][MAXN];
int main()
{
	n=read();m=read();s=read();t=read();
	for(int i=1;i<=m;++i)++a[read()],g[0][i]=1;
	g[0][0]=1;
	int cur=0;
	for(int i=1;i<=n;++i)
	{
		cur^=1;
		for(int j=0;j<=m;++j)
		{
			if(j<=a[i])f[cur][j]=g[cur^1][j];
			else f[cur][j]=(g[cur^1][j]-g[cur^1][j-a[i]-1]+MOD)%MOD;
			if(!j)g[cur][j]=f[cur][j];
			else g[cur][j]=(g[cur][j-1]+f[cur][j])%MOD;
		}
	}
	printf("%d\n",(g[cur][t]-g[cur][s-1]+MOD)%MOD);
	return 0;
}
